package org.example.leecode;

public class Leecode234 {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode secondList = reverse(slow);
        ListNode firstList = head;
        ListNode temp = secondList;
        //比较链表前半部分和后半部分
        while (temp != null){
            if(temp.val != firstList.val){
                return false;
            }
            firstList = firstList.next;
            temp = temp.next;
        }
        reverse(secondList);
        return true;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null){
            ListNode newTemp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = newTemp;
        }
        return pre;
    }

    class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
